import {
	TreeNode,
	BinaryTree
} from '../5.树/二叉树.js';

/**
 * 二叉排序树查找
 * @param {TreeNode} treeRoot 待查找的排序树的根节点
 * @param {Number} value 待查找结点值
 * @returns 如果查找到值等于待查找值的结点， 则返回该结点；如果树中没有该结点为指定值，则返回最后一个被查找（被比较）到的结点
 */
function searchNode(treeRoot, value) {
	// 如果当前结点值等于给定值则返回当前结点
	if (treeRoot.data === value) {
		return treeRoot;
	} else if (value > treeRoot.data && treeRoot.right != null) {
		// 如果给定值大于当前结点，则递归查找右子树
		return searchNode(treeRoot.right, value);
	} else if (value < treeRoot.data && treeRoot.left != null) {
		// 如果给定值小于当前结点，则递归查找左子树
		return searchNode(treeRoot.left, value);
	}
	// 到这里说明被查找结点不存在，就返回最后被比较的结点
	return treeRoot;
}

/**
 * 向二叉排序树插入一个结点
 *
 * @param {BinaryTree} tree  待插入结点的树
 * @param {Number} value 待插入的结点
 */
function insertNode(tree, value) {
	// 当前被比较结点，从根结点开始往下索引
	let current = searchNode(tree.root, value);
	// 如果当前遍历的集合值小于当前索引到树的结点值，则把当前值作为当前索引到结点的左孩子，否则作为右孩子
	let insertNode = new TreeNode(value, null, null, current);
	if (value < current.data) {
		current.left = insertNode;
	} else if (value > current.data) {
		current.right = insertNode;
	}
	// 相等则不作任何操作
}

/**
 * 从二叉排序树中删除一个结点
 *
 * @param {BinaryTree} tree  待删除结点的二叉排序树
 * @param {Number} value 待删除的值
 */
function deleteNode(tree, value) {
	// 先索引至被删除的结点的引用
	let current = searchNode(tree.root, value);
	// 若当前索引节点与给定值不符说明给定值不存在，返回
	if (current.data !== value) {
		return;
	}
	// 左子树为空则重接其右子树
	if (current.left == null) {
		// 判断自身是其双亲结点的左子树还是右子树
		if (current == current.parent.left) {
			current.parent.left = current.right;
		} else {
			current.parent.right = current.right;
		}
		current.parent = null;
	} else if (current.right == null) {
		// 右子树为空则重接其左子树
		// 判断自身是其双亲结点的左子树还是右子树
		if (current == current.parent.left) {
			current.parent.left = current.left;
		} else {
			current.parent.right = current.left;
		}
		current.parent = null;
	} else {
		// 左右子树都不空
		// 先索引到其左子树最大的结点
		let leftMax = current.left;
		while (leftMax.right != null) {
			leftMax = leftMax.right;
		}
		// 令被删除结点的值域等于左子树最大结点
		current.data = leftMax.data;
		// 然后删除左子树最大结点（这个结点只会是存在左子树或者右子树之一，不可能左右子树同时存在）
		// 还是上面的判断逻辑
		if (leftMax.left == null) {
			if (leftMax == leftMax.parent.left) {
				leftMax.parent.left = leftMax.right;
			} else {
				leftMax.parent.right = leftMax.right;
			}
		} else if (leftMax.right == null) {
			if (leftMax == leftMax.parent.left) {
				leftMax.parent.left = leftMax.left;
			} else {
				leftMax.parent.right = leftMax.left;
			}
		}
		leftMax.parent = null;
	}
}

/**
 * 把一个无序整数集合构造成二叉排序树
 *
 * @param {Array<Number>} originList 原始无序整数集合
 * @returns 构造的二叉排序树
 */
function createSortTree(originList) {
	// 把集合中的第一个元素作为二叉排序树的根结点
	let tree = new BinaryTree(new TreeNode(originList[0], null, null, null));
	// 遍历集合开始插入，从第2个开始
	for (let i = 1; i < originList.length; i++) {
		insertNode(tree, originList[i]);
	}
	return tree;
}

// 测试
let originList = [45, 12, 3, 37, 24, 100, 53, 61, 90, 78];
let tree = createSortTree(originList);
let preList = tree.preorderTraversal();
let inList = tree.inorderTraversal();
// 打印先序遍历
console.log(preList);
// 打印中序遍历
console.log(inList);
// 删除一个结点试试
deleteNode(tree, 45);
preList = tree.preorderTraversal();
inList = tree.inorderTraversal();
// 打印先序遍历
console.log(preList);
// 打印中序遍历
console.log(inList);